package com.zzh.tree;
//给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
//
// 说明: 叶子节点是指没有子节点的节点。
//
// 示例:
//给定如下二叉树，以及目标和 sum = 22，
//
//               5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \    / \
//        7    2  5   1
//
//
// 返回:
//
// [
//   [5,4,11,2],
//   [5,8,4,5]
//]
//
// Related Topics 树 深度优先搜索
// 👍 281 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
public class No113_pathSum {
    public static void main(String[] args) {
        No113Solution solution = new No113Solution();
        List<List<Integer>> lists = solution.pathSum(TreeNode.initTree(), 3);
        for (List list:lists){
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}
class No113Solution{
    private int tar;
    private List<List<Integer>> lists=new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root==null){
            //特殊处理
            return new LinkedList<>();
        }
        tar=sum;
        //回溯
        dfs(root,0,new LinkedList<>());
        return lists;
    }
    public void dfs(TreeNode root, int sum, LinkedList<Integer> temp){
        if (root.left==null&&root.right==null){
            //到达叶子结点，计算是否符合条件
            if (sum+root.val==tar){
                //将新结点的值加入到list中
                temp.add(root.val);
                lists.add(new LinkedList<>(temp));
                temp.removeLast();//恢复现场，供下一次回溯使用
            }
            return;
        }
        temp.add(root.val);
        if (root.left!=null){
            dfs(root.left,sum+root.val,temp);
        }
        if (root.right!=null){
            dfs(root.right,sum+root.val,temp);
        }
        //恢复供下次继续使用
        temp.removeLast();
    }
}
